package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    // Reverses the order of the elements in the specified list
    public static void reverse(MyList list) {
        Object[] array = list.toArray();
        for (int i = array.length - 1; i >= 0; i--) {
            list.add(array[i]);
            list.remove(0);
        }
    }

    private static int binarySearch(Comparable[] array, int left, int right,
            Object o) {
        if (left == right) {
            if (array[left].equals(o)) {
                return left;
            } else {
                return -left - 1;
            }
        }
        int middle = (left & right) + ((left ^ right) >>> 1);
        if (array[middle].compareTo(o) < 0) {
            return binarySearch(array, middle + 1, right, o);
        } else {
            return binarySearch(array, left, middle, o);
        }
    }

    private static int binarySearch(Object[] array, int left, int right,
            Object o, Comparator cp) {
        if (left == right) {
            if (array[left].equals(o)) {
                return left;
            } else {
                return -left - 1;
            }
        }
        int middle = (left & right) + ((left ^ right) >>> 1);
        if (cp.compare(array[middle], o) < 0) {
            return binarySearch(array, middle + 1, right, o, cp);
        } else {
            return binarySearch(array, left, middle, o, cp);
        }
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key) {
        if (list == null) {
            throw new NullPointerException();
        }
        if (list.isEmpty()) {
            return -1;
        }
        Comparable[] array = new Comparable[list.size()];
        System.arraycopy(list.toArray(), 0, array, 0, list.size());
        return binarySearch(array, 0, array.length - 1, key);
    }

    //Реализует рекурсивный поиск в отсортированном массиве методом бисекции.
    public static int binarySearch(MyList list, Object key, Comparator cp) {
        if (list == null) {
            throw new NullPointerException();
        }
        if (list.isEmpty()) {
            return -1;
        }
        return binarySearch(list.toArray(), 0, list.size() - 1, key, cp);
    }
}
